#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define ff first
#define ss second

int n, m, D;
int c[100][100], a[100][100], dp[100][101];
int usd, was[100][101], inf;

int NUM;
int d[100][100];

inline bool less2(int i, int j)
{
	return d[NUM][i] < d[NUM][j] || (d[NUM][i] == d[NUM][j] && i < j);
}

vector <pair <int, int> > next[101];
int heap[103];
int id[103];
int size;

inline void Swap(int i, int j)
{
	swap(heap[i], heap[j]);
	swap(id[heap[i]], id[heap[j]]);
}


void checkUp(int pos)
{
	while (pos > 1)
	{
		if (less2(heap[pos], heap[pos >> 1]))
		{
			Swap(pos, pos >> 1);
			pos >>= 1;
		}
		else break;
	}
}

void checkDown(int pos)
{
	int l, r, t;
	while (true)
	{
		t = pos;
		l = t << 1;
		r = l | 1;
		if (l <= size && less2(heap[l], heap[t]))
			t = l;
		if (r <= size && less2(heap[r], heap[t]))
			t = r;
		if (t == pos) break;
		Swap(t, pos);
		pos = t;
	}
}


inline int extMin()
{
	return heap[1];
}

inline void insert(int key)
{
	++size;
	id[key] = size;
	heap[size] = key;
	checkUp(size);
}

inline void erase(int key)
{
	int pos = id[key];
	Swap(pos, size);
	id[key] = 0;
	size--;
	checkUp(pos);
	checkDown(pos);
}

inline bool contains(int key)
{
	return id[key] != 0;
}


const int MAGIC = 13;

void FastFloyd()
{
	for (int i = 0; i < m; i++)
	{
		next[i].resize(m);
		for (int j = 0; j < m; j++)
		{
			next[i][j].ff = c[i][j];
			next[i][j].ss = j;
		}
	    sort (next[i].begin(), next[i].end());
	}

	for (int i = 0; i < m; i++)
		for (int j = 0; j < m; j++)
			d[i][j] = inf;

	int M;
	M = min (MAGIC, m);
	int v;
	for (NUM = 0; NUM < m; NUM++)
	{
		d[NUM][NUM] = 0;
		//v.i = NUM;
		insert(NUM);
		while (size)
		{
			v = extMin();
			erase(v);
			//st.erase (st.begin());
			for (int j = 0; j < M; j++)
				if (d[NUM][next[v][j].second] > d[NUM][v] + next[v][j].first)
				{
					if (contains(next[v][j].second))
						erase(next[v][j].second);
					d[NUM][next[v][j].second] = d[NUM][v] + next[v][j].first;
					insert(next[v][j].second);
				}
		}

	}
	for (int i = 0; i < m; i++)
		for (int j = 0; j < m; j++)
			c[i][j] = d[i][j];
}





void load()
{
	scanf("%d%d%d", &D, &n, &m);
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &a[i][j]);
	for (int i = 0; i < m; i++)
		for (int j = 0; j < m; j++)
			scanf("%d", &c[i][j]);
    inf = D + 1;
    //for (int i = 0; i < m; i++)
      //  for (int j = 0; j <= n; j++)
        //    dp[i][j] = -1;
}

int f(int i, int j)
{
    if (j == n) return 0;
    if (was[i][j] == usd) return dp[i][j];
    was[i][j] = usd;
    dp[i][j] = inf;
    for (int k = 0; k < m; k++)
    {
        dp[i][j] = min(dp[i][j], f(k, j + 1) + a[k][j] + c[i][k]);
    }
    return dp[i][j];
}

void solve()
{
	usd++;
	FastFloyd();
/*    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < m; k++)
                c[j][k] = min(c[j][k], c[j][i] + c[i][k]);
                */
    int res = inf;
    for (int i = 0; i < m; i++)
        res = min(res, f(i, 0));
    printf("%d\n", D - res);
}

int main()
{
//	freopen("gift.in", "rt", stdin);
//	freopen("gift.out", "wt", stdout);

	int T;
	scanf("%d", &T);
	for (int i = 0; i < T; i++)
	{
		load();
		solve();
	}
	return 0;
}